package tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TreeNode {
    public int val;
    public TreeNode left = null;
    public TreeNode right = null;
    public List<Integer> data; // only in root
    public TreeNode(int x) {
        val = x;
    }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static TreeNode buildTree(List<Integer> list) {
        if (list == null || list.isEmpty()) {
            return null;
        }
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = new TreeNode(list.get(0));
        q.offer(root);

        int index = 1;
        while (!q.isEmpty() && index < list.size()) {
            int count = q.size();
            for (int i = 0; i < count; i++) {
                TreeNode parent = q.poll();
                if (index < list.size()) {
                    if (list.get(index) != null) {
                        parent.left = new TreeNode(list.get(index));
                        q.offer(parent.left);
                    }
                    index++;
                }
                if (index < list.size()) {
                    if (list.get(index) != null) {
                        parent.right = new TreeNode(list.get(index));
                        q.offer(parent.right);
                    }
                    index++;
                }
            }
        }
        return root;
    }

    @Override
    public String toString() {
        return "TreeNode{" + "val=" + val + '}';
    }

    /*
    public static TreeNode buildTree(List<Integer> list) {
        TreeNode[] nodes = new TreeNode[list.size()];
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) != null) {
                nodes[i] = new TreeNode(list.get(i));
                int parent = (i-1)/2;
                boolean isLeft = ((i-1) % 2 == 0);
                if (isLeft) {
                    nodes[parent].left = nodes[i];
                } else {
                    nodes[parent].right = nodes[i];
                }
            }
        }
        nodes[0].data = list;
        return nodes[0];
    }
    */
}